home *** CD-ROM | disk | FTP | other *** search
/ MacTech 1 to 12 / MacTech-vol-1-12.toast / Source / MacTech® Magazine / Volume 09 - 1993 / 09.07 Jul 93 / Bedrock Header Files / Support Includes / BRVMBest.h < prev    next >
Encoding:
Text File  |  1993-04-19  |  9.4 KB  |  424 lines  |  [TEXT/MPS ]
  1. // BRVMBest.h 
  2. // Copyright © 1985-1992 by Apple Computer, Inc.  All rights fReserved.
  3.  
  4. #ifndef BRVMBEST_H
  5. #define BRVMBEST_H
  6.  
  7. #ifndef BRSUPDEF_H
  8. #include "BRSupDef.h"
  9. #endif
  10.  
  11. #ifndef BRVMHEAP_H
  12. #include "BRVMHeap.h"
  13. #endif
  14.  
  15.  
  16. //========================================================================================
  17. // CLASS BR_CBestFitBlock
  18. //========================================================================================
  19.  
  20. class BR_CBestFitBlock
  21. {
  22. public:
  23.     enum
  24.     {
  25.         kBusyOverhead = 4, 
  26.         kMinBlockSize = 20, 
  27.         kBestFitBlockType = 1, 
  28.         kMaxBlockSize = 0x00FFFFFF, 
  29.         kMagicNumber = 0x3
  30.     };
  31.  
  32.  
  33.     BR_Boolean operator>(const BR_CBestFitBlock& blk);
  34.     BR_Boolean operator<(const BR_CBestFitBlock& blk);
  35.     BR_Boolean operator>=(const BR_CBestFitBlock& blk);
  36.     BR_Boolean operator<=(const BR_CBestFitBlock& blk);
  37.     BR_Boolean operator==(const BR_CBestFitBlock& blk);
  38.     BR_Boolean operator!=(const BR_CBestFitBlock& blk);
  39.  
  40.     void operator delete(void*);
  41.     void* operator new(size_t,
  42.                        void* ptr);
  43.     void* operator new(size_t);
  44.  
  45.     BR_CBestFitBlock();
  46.     BR_CBestFitBlock(int busy,
  47.                      int prevBusy,
  48.                      long size);
  49.  
  50.     ~BR_CBestFitBlock();
  51.  
  52.     BR_Boolean GetBusy();
  53.     BR_CBestFitBlock* GetLeft();
  54.     unsigned int GetMagicNumber();
  55.     BR_CBestFitBlock* GetNext();
  56.     BR_CBestFitBlock* GetParent();
  57.     BR_Boolean GetPreviousBusy();
  58.     BR_CBestFitBlock* GetRight();
  59.     BR_MemoryBlockSize GetSize();
  60.  
  61.     void SetBusy(BR_Boolean busy);
  62.     void SetLeft(BR_CBestFitBlock* left);
  63.     void SetNext(BR_CBestFitBlock* fNext);
  64.     void SetParent(BR_CBestFitBlock* parent);
  65.     void SetPrevBusy(BR_Boolean busy);
  66.     void SetRight(BR_CBestFitBlock* right);
  67.     void SetSize(BR_MemoryBlockSize size);
  68.  
  69.     void StuffAddressAtEnd();
  70.  
  71. protected:
  72.  
  73. private:
  74.  
  75.     // The following four fields are present in both free blocks and busy blocks.
  76.     // Block sizes are limited to sizes that can be represented in 24 bits (16 Meg).
  77.     // The fBlockType field distiguishes chunky blocks from best fit blocks and
  78.     // must be the first bit of the last byte in the header of both best fit and
  79.     // chunky blocks.
  80.  
  81.     BR_MemoryBlockSize fSize:24;
  82.     int fBlockType:4;
  83.     BR_Boolean fBusy:1;
  84.     BR_Boolean fPreviousBusy:1;
  85.  
  86.     unsigned int fMagicNumber:2;
  87.  
  88.     // The following fields are only present in free blocks. They are used to link
  89.     // the free block into the free block tree. The address of a free block is also
  90.     // stored at the fEnd of the block and must be accounted for in the minimum block
  91.     // size.
  92.  
  93.     BR_CBestFitBlock* fParent;
  94.     BR_CBestFitBlock* fLeft;
  95.     BR_CBestFitBlock* fRight;
  96. };
  97.  
  98. //----------------------------------------------------------------------------------------
  99. // INLINES BR_CBestFitBlock
  100. //----------------------------------------------------------------------------------------
  101.  
  102. //inline void BR_CBestFitBlock::operator delete(void*)
  103. //{
  104. //}
  105.  
  106.  
  107. inline void* BR_CBestFitBlock::operator new(size_t,
  108.                                             void* ptr)
  109. {
  110.     return ptr;
  111. }
  112.  
  113.  
  114. inline void* BR_CBestFitBlock::operator new(size_t)
  115. {
  116.     return NULL;
  117. }
  118.  
  119.  
  120. inline BR_Boolean BR_CBestFitBlock::operator>=(const BR_CBestFitBlock& blk)
  121. {
  122.     return *this > blk || *this == blk;
  123. }
  124.  
  125.  
  126. inline BR_Boolean BR_CBestFitBlock::operator<=(const BR_CBestFitBlock& blk)
  127. {
  128.     return *this < blk || *this == blk;
  129. }
  130.  
  131.  
  132. inline BR_Boolean BR_CBestFitBlock::operator!=(const BR_CBestFitBlock& blk)
  133. {
  134.     return !(*this == blk);
  135. }
  136.  
  137.  
  138. inline BR_CBestFitBlock::BR_CBestFitBlock(int busy,
  139.                                           int previousBusy,
  140.                                           long size)
  141. {
  142.     fParent = NULL;
  143.     fRight = fLeft = NULL;
  144.     fBlockType = kBestFitBlockType;
  145.     fBusy = busy;
  146.     fPreviousBusy = previousBusy;
  147.     fSize = size;
  148.     fMagicNumber = kMagicNumber;
  149.  
  150.     if (!busy)
  151.         this->StuffAddressAtEnd();
  152. }
  153.  
  154.  
  155. inline BR_CBestFitBlock::BR_CBestFitBlock()
  156. {
  157.     fParent = NULL;
  158.     fRight = fLeft = NULL;
  159.     fBlockType = kBestFitBlockType;
  160.     fBusy = FALSE;
  161.     fPreviousBusy = FALSE;
  162.     fSize = 0;
  163.     fMagicNumber = kMagicNumber;
  164.  
  165.     this->StuffAddressAtEnd();
  166. }
  167.  
  168.  
  169. inline BR_CBestFitBlock::~BR_CBestFitBlock()
  170. {
  171. }
  172.  
  173.  
  174. inline BR_Boolean BR_CBestFitBlock::GetBusy()
  175. {
  176.     return fBusy;
  177. }
  178.  
  179.  
  180. inline BR_CBestFitBlock* BR_CBestFitBlock::GetLeft()
  181. {
  182.     return fLeft;
  183. }
  184.  
  185.  
  186. inline unsigned int BR_CBestFitBlock::GetMagicNumber()
  187. {
  188.     return fMagicNumber;
  189. }
  190.  
  191.  
  192. inline BR_CBestFitBlock* BR_CBestFitBlock::GetNext()
  193. {
  194.     return fParent;
  195. }
  196.  
  197.  
  198. inline BR_CBestFitBlock* BR_CBestFitBlock::GetParent()
  199. {
  200.     return fParent;
  201. }
  202.  
  203.  
  204. inline BR_Boolean BR_CBestFitBlock::GetPreviousBusy()
  205. {
  206.     return fPreviousBusy;
  207. }
  208.  
  209.  
  210. inline BR_CBestFitBlock* BR_CBestFitBlock::GetRight()
  211. {
  212.     return fRight;
  213. }
  214.  
  215.  
  216. inline BR_MemoryBlockSize BR_CBestFitBlock::GetSize()
  217. {
  218.     return fSize;
  219. }
  220.  
  221.  
  222. inline void BR_CBestFitBlock::SetBusy(BR_Boolean busy)
  223. {
  224.     fBusy = busy;
  225. }
  226.  
  227.  
  228. inline void BR_CBestFitBlock::SetLeft(BR_CBestFitBlock* left)
  229. {
  230.     fLeft = left;
  231. }
  232.  
  233.  
  234. inline void BR_CBestFitBlock::SetNext(BR_CBestFitBlock* fNext)
  235. {
  236.     fParent = fNext;
  237. }
  238.  
  239.  
  240. inline void BR_CBestFitBlock::SetParent(BR_CBestFitBlock* parent)
  241. {
  242.     fParent = parent;
  243. }
  244.  
  245.  
  246. inline void BR_CBestFitBlock::SetPrevBusy(BR_Boolean busy)
  247. {
  248.     fPreviousBusy = busy;
  249. }
  250.  
  251.  
  252. inline void BR_CBestFitBlock::SetRight(BR_CBestFitBlock* right)
  253. {
  254.     fRight = right;
  255. }
  256.  
  257.  
  258. inline void BR_CBestFitBlock::SetSize(BR_MemoryBlockSize size)
  259. {
  260.     fSize = size;
  261. }
  262.  
  263.  
  264. //========================================================================================
  265. // CLASS BestFitHeap
  266. //
  267. //        The BestFitHeap allocates fMemory from the system in segments. The segments are
  268. //        linked together in a list so that When the heap is destroyed all segments can be
  269. //        freed.
  270. //
  271. //========================================================================================
  272.  
  273. class BR_CBestFitSegment
  274. {
  275. public:
  276.  
  277.     friend BR_CBestFitHeap;
  278.  
  279.     enum
  280.     {
  281.         kSegmentPrefixSize = 12, kSegmentSuffixSize = 4, kSegmentOverhead = kSegmentPrefixSize + kSegmentSuffixSize
  282.     };
  283.  
  284.  
  285.     inline BR_Boolean AddressInSegment(void* ptr);
  286.  
  287. protected:
  288.  
  289. private:
  290.     void* fSegmentSpace;
  291.     BR_MemoryBlockSize fSegmentSize;
  292.     BR_CBestFitSegment* fNextSegment;
  293. };
  294.  
  295. //----------------------------------------------------------------------------------------
  296. // INLINES BR_CBestFitSegment
  297. //----------------------------------------------------------------------------------------
  298.  
  299. inline BR_Boolean BR_CBestFitSegment::AddressInSegment(void* ptr)
  300. {
  301. #ifdef BR_BUILD_MAC
  302.     return ptr >= fSegmentSpace && ptr <= (void*)((BR_PointerDifference)fSegmentSpace + fSegmentSize);
  303. #endif
  304. #ifdef BR_BUILD_WIN
  305.     return ptr >= fSegmentSpace && ptr <= (void*)((long)fSegmentSpace + fSegmentSize);
  306. #endif
  307.  
  308. }
  309.  
  310.  
  311. //========================================================================================
  312. // CLASS BR_CFreeBlockTreeStats
  313. //
  314. //        Keep statistics on the min, max, and average size and depth of the
  315. //        free block list.
  316. //
  317. //========================================================================================
  318.  
  319. class BR_CFreeBlockTreeStats
  320. {
  321. };
  322.  
  323. //========================================================================================
  324. // CLASS BR_CFreeBlockTree
  325. //
  326. //        Binary tree for storing free blocks. Dependent on the structure and
  327. //        implementation of BR_CBestFitBlock.
  328. //
  329. //========================================================================================
  330.  
  331. class BR_CFreeBlockTree
  332. {
  333. public:
  334.     BR_CFreeBlockTree();
  335.  
  336.     void AddBlock(BR_CBestFitBlock* blk);
  337.     void TreeInfo(BR_MemoryBlockSize& bytesFree,
  338.                   BR_MemoryBlockSize& numberOfNodes) const;
  339.     void CheckTree() const;
  340.     void PrintTree() const;
  341.     void RemoveBlock(BR_CBestFitBlock* blk);
  342.     BR_CBestFitBlock* SearchForBlock(BR_MemoryBlockSize size,
  343.                                      void* blk,
  344.                                      BR_CBestFitBlock** insertLeaf = NULL);
  345.     void TreeInfo(BR_MemoryBlockSize& bytesFree,
  346.                   BR_MemoryBlockSize& numberOfNodes);
  347.  
  348.     ~BR_CFreeBlockTree();
  349.  
  350. protected:
  351.     void CheckTreeHelper(BR_CBestFitBlock* blk) const;
  352.     BR_CBestFitBlock* GetSuccessorBlk(BR_CBestFitBlock* blk);
  353.     void PrintTreeHelper(BR_CBestFitBlock* blk,
  354.                          int level = 0) const;
  355.     void TreeInfoHelper(BR_CBestFitBlock* blk,
  356.                         BR_MemoryBlockSize& bytesFree,
  357.                         BR_MemoryBlockSize& numberOfNodes) const;
  358.  
  359. private:
  360.     BR_CBestFitBlock fRoot;
  361.  
  362. #ifdef BR_DEBUG
  363.     BR_CFreeBlockTreeStats fStats;
  364. #endif
  365.  
  366. };
  367.  
  368. //----------------------------------------------------------------------------------------
  369. // INLINES BR_CFreeBlockTree
  370. //----------------------------------------------------------------------------------------
  371.  
  372. inline BR_CFreeBlockTree::~BR_CFreeBlockTree()
  373. {
  374. }
  375.  
  376.  
  377. //========================================================================================
  378. // CLASS BR_CBestFitHeap
  379. //
  380. //        Memory allocation heap using the best fit allocation strategy.
  381. //
  382. //========================================================================================
  383.  
  384. class BR_CBestFitHeap : public BR_CMemoryHeap
  385. {
  386. public:
  387.  
  388.     virtual BR_MemoryBlockSize BytesFree() const;
  389.     virtual void Check() const;
  390.     virtual void* DoAllocate(BR_MemoryBlockSize size,
  391.                              BR_MemoryBlockSize& allocatedSize);
  392.     virtual BR_MemoryBlockSize DoBlockSize(const void* block) const;
  393.     virtual void DoFree(void*);
  394.     virtual BR_Boolean DoIsValidBlock(void* blk) const;
  395.     virtual void DoReset();
  396.     virtual BR_MemoryBlockSize HeapSize() const;
  397.     virtual BR_Boolean IsMyBlock(void* blk) const;
  398.     virtual void Print(char* msg = "") const;
  399.  
  400.     BR_CBestFitHeap(BR_MemoryBlockSize sizeInitial,
  401.                     BR_MemoryBlockSize sizeIncrement = 0);
  402.     virtual~ BR_CBestFitHeap();
  403.  
  404. protected:
  405.  
  406.     void AddToFreeBlocks(BR_CBestFitBlock* blk);
  407.     BR_CBestFitBlock* Coalesce(BR_CBestFitBlock* blk);
  408.     void CreateNewSegment(BR_MemoryBlockSize size);
  409.     void DeleteSegments();
  410.     void RemoveFromFreeBlocks(BR_CBestFitBlock* blk);
  411.     BR_CBestFitBlock* SearchFreeBlocks(BR_MemoryBlockSize size);
  412.  
  413. private:
  414.  
  415.     BR_CBestFitSegment* fSegments;
  416.     BR_MemoryBlockSize fSizeIncrement;
  417.     BR_MemoryBlockSize fSizeInitial;
  418.     BR_CFreeBlockTree fFreeTree;
  419. };
  420.  
  421.  
  422.  
  423. #endif
  424.